maze = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
    [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]

dirs = [
    lambda x, y: (x+1, y),
    lambda x, y: (x-1, y),
    lambda x, y: (x, y-1),
    lambda x, y: (x, y+1),
]


def maze_path(x1, y1, x2, y2):
    """
    :param x1: 起点x1
    :param y1: 起点y1
    :param x2: 终点x2
    :param y2: 终点y2
    :return:
    """
    stack = []
    stack.append((x1, y1))
    while len(stack) > 0:
        cur_node = stack[-1]
        if cur_node[0] == x2 and cur_node[1] == y2:
            # 走到终点了
            for p in stack:
                print(p, end='->')
            print('\b\b')
            return True
        # 四个方向
        for dir in dirs:
            next_node = dir(cur_node[0], cur_node[1])
            # 如果下一个结点能走
            if maze[next_node[0]][next_node[1]] == 0:
                stack.append(next_node)
                # 标记已经走过
                maze[next_node[0]][next_node[1]] = 2
                break
        else:
            maze[next_node[0]][next_node[1]] = 2
            stack.pop()
    else:
        print('No Ways In This Maze.')
        return False


maze_path(1, 1, 8, 8)
# (1, 1)->(2, 1)->(3, 1)->(4, 1)->(5, 1)->(5, 2)->(5, 3)->(6, 3)->(6, 4)->(6, 5)->(7, 5)->(8, 5)->(8, 6)->(8, 7)->(8, 8)
